package q146;

import java.util.*;

/**
 * LRU缓存
 */
public class LRUCache {

    int capacity = 0;
    transient int count = 0;
    Map<Integer, Element> map = new HashMap<>();
    PriorityQueue<Element> pq = new PriorityQueue<>(Comparator.comparing(e -> e.count));

    public LRUCache(int capacity) {
        this.capacity = capacity;
    }

    public int get(int key) {
        if (!map.containsKey(key)) return -1;
        map.get(key).count = this.count ++;
        rebuild(key);
        return map.get(key).value;
    }

    public void put(int key, int value) {
        if (map.containsKey(key)) {
            map.get(key).value = value;
            map.get(key).count = this.count ++;
            rebuild(key);
        } else {
            if (capacity <= map.size()) {
                map.remove(pq.poll().key);
            }

            map.put(key, new Element(key,value, this.count ++));
            pq.offer(map.get(key));
        }
    }

    public void rebuild(Integer key) {
        pq.remove(map.get(key));
        pq.offer(map.get(key));
    }

    public static class Element {
        public Element(Integer key, Integer value, Integer count) {
            this.key = key;
            this.value = value;
            this.count = count;
        }
        Integer key;
        Integer value;
        Integer count;
    }
}
